package com.huangpeng.algorithm.snowFlake;

/**
 * @Author huangpeng
 * @Title 删除链表中重复怒的结点。  在一个排序的链表中，如何删除重复的结点？  比如，链表1→2→3→3→4→4→5，删除重复结点后为：1→2→5。
 * @Package
 * @Date 2021/5/21 14:34
 * @Description
 * @Version 1.0
 */
public class DeleteDuplication {
    private int value;
    private DeleteDuplication next;

    public DeleteDuplication() {
    }

    public DeleteDuplication(int value, DeleteDuplication next) {
        this.value = value;
        this.next = next;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public DeleteDuplication getNext() {
        return next;
    }

    public void setNext(DeleteDuplication next) {
        this.next = next;
    }

    public static void main(String[] args) {
        DeleteDuplication head = init();
        forwardPrint(head);
        head = deleteDuplication(head);
        forwardPrint(head);
    }

    public static DeleteDuplication init() {
        DeleteDuplication node7 = new DeleteDuplication(5, null);
        DeleteDuplication node6 = new DeleteDuplication(4, node7);
        DeleteDuplication node5 = new DeleteDuplication(4, node6);
        DeleteDuplication node4 = new DeleteDuplication(3, node5);
        DeleteDuplication node3 = new DeleteDuplication(3, node4);
        DeleteDuplication node2 = new DeleteDuplication(2, node3);
        DeleteDuplication node1 = new DeleteDuplication(1, node2);
        return node1;
    }

    public static void forwardPrint(DeleteDuplication head) {
        DeleteDuplication node = head;
        while (node != null) {
            System.out.print(node.getValue() + "->");
            node = node.getNext();
        }
        System.out.println();
    }

    public static DeleteDuplication deleteDuplication(DeleteDuplication head) {
        if (head == null) {
            return null;
        }
        DeleteDuplication prev = null;
        DeleteDuplication node = head;
        while (node != null) {
            DeleteDuplication next = node.getNext();
            if (next != null && next.getValue() == node.getValue()) {
                int value = node.getValue();
                while (node != null && node.getValue() == value) {// 多个重复的结点在一起
                    DeleteDuplication deleteNode = node;
                    node = node.getNext();
                    deleteNode = null;
                }
            } else {
                prev = node;
                node = next;
            }
            if (prev == null) {// 头结点是重复的结点
                head = node;
            } else {
                prev.setNext(node);
            }
        }
        return head;
    }
}
